A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form.
Certain devices within the network referred to as routers use routing protocols to exchange and accumulate topology information that describes the network. This allows a router to construct its own routing topology map of the network. Upon receiving an incoming data packet, the router examines keying information within the packet and forwards the packet in accordance with the accumulated topology information.
Many routing protocols fall within a protocol class referred to as Interior Gateway Protocol (IGP) in which flooding-based distribution mechanisms are used to announce topology information to routers within the network. These routing protocols typically rely on routing algorithms that require each of the routers to have synchronized routing topology information for a given domain, referred to as the IGP area. The contents of a Link State Database (LSDB) or a Traffic Engineering Database (TED) maintained in accordance with a link state routing protocol only have the scope of an IGP area. IPG routing protocols typically require that all routers in the IGP routing domain store within an internal LSDB or TED all of the routing information that has been distributed according to the IGP protocol. In this way, the routers are able to select paths that are consistent and loop-free. Further, the ubiquity of the routing information allows the flooding process to be reliable, efficient and guaranteed to terminate. In operation, each router typically maintains an internal link state database and scans the entire database at a defined interval to generate and output link state messages so as to synchronize the database to neighboring routers within the routing domain. In this way, link state is propagated across the entire routing domain and stored in full at each router within the domain.
Open Shortest Path First (OSPF) and Intermediate system to intermediate system (IS-IS) are example link state protocols that use link state messages to ensure their routing topology is synchronized with respect to available interfaces, metrics and other variables associated with network links OSPF utilizes Link State Advertisements (LSAs) while IS-IS uses Link State Protocol Data Units (LSPs) to exchange information. In network topologies where routers are connected by point-to-point connections, each router floods link state messages to adjacent routers reachable on each interface to ensure synchronization. In networks using multi-access media, such as an Ethernet network, the routers within the network flood the link state messages to all other routers. In either case, the receiving routers construct and maintain their own network topologies using the link information received via the link state messages. IS-IS is specified in “Intermediate system to Intermediate system routing information exchange protocol for use in conjunction with the Protocol for providing the Connectionless-mode Network Service (ISO 8473),” ISO, ISO/IEC 10589:2002, the entire contents of which is incorporated herein by reference.
Packet-based networks increasingly utilize label switching protocols for traffic engineering and other purposes. Multi-Protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks according to the routing information maintained by the routers in the networks. By utilizing MPLS protocols, such as the Label Distribution protocol (LDP) or the Resource Reservation Protocol (RSVP) with Traffic Engineering extensions (RSVP-TE), label switching routers can forward traffic along a particular path through a network to a destination device, i.e., a Label Switched Path (LSP), using labels prepended to the traffic. An LSP defines a distinct path through the network to carry MPLS packets from the source device to a destination. Using a MPLS protocol, each router along an LSP allocates a label in association with the destination and propagates the label to the closest upstream router along the path. Routers along the path add or remote the labels and perform other MPLS operations to forward the MPLS packets along the established path.
MPLS with traffic engineering (MPLS-TE) applies constraint based routing to costs and resource availability for network links within a routing domain to select LSP paths within the routing domain. In conventional network environments, a router or path computation element (PCE) external to one or more IGP routing domains is typically unable to compute a MPLS-TE path across and through multiple IGP areas because the device's own IGP Traffic Engineering Database (TED) lacks visibility of the complete topology, i.e., the costs and resource availability for the individual links within each of the IGP routing domains. As a result, the router is typically unable to determine a complete end-to-end path, and is often unable to even select optimal exit routers for each routing domain so as to create an optimal path. This may be problematic for large-scale networks that need to segment their core networks into distinct routing areas, but which still want to take advantage of MPLS-TE.
Previous solutions used per-domain path computation in which a respective router or PCE associated with each IGP routing domain computed the internal path for the corresponding routing domain. In such implementations, the source router could only compute the path for the first area because the router only has full topological visibility (e.g., link state, costs and utilization) within the first area along the path, but not for subsequent areas. Per-domain path computation uses, for example, a technique called “loose-hop-expansion”, and selects the exit ABR and other ABRs or AS Border Routers (ASBRs) using the IGP computed shortest path topology for the remainder of the path. This may lead to sub-optimal paths, makes alternate/back-up path computation hard, and might result in no TE path being found even in situations where one actually exists.